Código a ejecutar para empezar (de clic en donde en dice “Code”, para desplegar el código, y luego copie y pegue en una sesión abierta de R):
Code
# cambia idioma de la consola de R a español:Sys.setenv(LANG="es")# usar 2 cifras significativas y tiende a evitar # notación científica (ver ayuda de función: `options`): options(digits =2, scipen =999) # cargar librerías: if(!require(igraph)){install.packages("igraph"); library(igraph)}if(!require(sand)){install.packages("sand"); library(sand)}
Introducción
Se quiere caracterizar aspectos fundamentales de la estructura social de una red representada por medio de un grafo G=(V,E):
Importancia de individuos.
Dinámicas sociales.
Flujo de la información.
Formación de comunidades.
Grado y fuerza
El grado (degree) d_v de un vértice v\in V se define como d_v=|\left\{\{v,u\}\in E:u\in V \right\}|, i.e., d_v corresponde al número de aristas incidentes en v.
A partir de la matriz de adyacencia\mathbf{Y}=[y_{i,j}] se tiene que el grado del individuo i se puede calcular mediante
El grado de un vértice es la combinación de la sociabilidad y la popularidad.
¿Cómo se adaptan estos conceptos en el caso de los digrafos?
En redes ponderadas, la fuerza (strength) s_v de un vértice v\in V se define como
s_v = \sum_{u\in V:\{v,u\}\in E} w_{\{v,u\}}\,,
i.e., la suma de los pesos de las aristas incidentes en v.
Ejemplo: Reforma Tributaria en Colombia.
Red de influencia en Twitter (ahora X) sobre la Reforma Tributaria en Colombia, en el contexto de su aprobación en el Congreso.
Estos datos fueron recolectados para estudiar las dinámicas de interacción entre usuarios de la red social, en relación con las opiniones sobre la Reforma Tributaria.
Los usuarios están conectados mediante aristas ponderadas por el número de interacciones (tuits, retuits, citas y comentarios) relacionadas con el tema.
El artículo asociado a estos datos puede ser encontrado aquí.
# matriz de adyacenciaY <-as_adjacency_matrix(g, sparse = F)# gradohead(cbind(degree(graph = g), apply(X = Y, MARGIN =1, FUN = sum), apply(X = Y, MARGIN =2, FUN = sum)), n =5)
La distribución del grado (degree distribución) de G es la colección de frecuencia relativas f_0, f_1,\ldots, donde
f_d = \frac{|\{v\in V:d_v = d\}|}{|V|}\,,\qquad \text{para}\,\,d=0,1,\ldots\,,
i.e., la fracción de vértices en V tales que d_v = d.
La distribución de fuerza (strength distribution) se define de manera análoga.
Visualización
En este gráfico se observa que la mayoría de los individuos tienen un grado bajo, mientras que un grupo reducido presenta un grado elevado. Estos últimos corresponden a figuras altamente influyentes, como el presidente Petro, cuya importancia ya había sido destacada previamente.
Code
par(mfrow =c(1,2))# Gráfico de barras (distribución del grado)plot(table(factor(d, levels =0:n)) / n, type ="h", lwd =5, xlab ="Grado", ylab ="Densidad", xlim =c(0, max(d)), ylim =c(0, max(table(factor(d, levels =0:n)) / n)), main ="", xaxt ="n", col ="gray50")axis(side =1, at =seq(from =0, to =max(d), by =5)) # Ajustar el eje x automáticamente# Histograma (densidad del grado)plot(NA, NA, type ="n", xlim =c(min(d), max(d)), ylim =c(0, 0.4), xlab ="Grado", ylab ="Densidad", main ="")hist(d, freq =FALSE, col ="gray90", border ="gray50",add =T)# Título generaltitle(main ="Distribución del grado", outer =TRUE, line =-2)
Ley de potencias
En algunas redes se tiene que una gran porción de vértices tiene grado bajo y una pequeña fracción tiene grado alto. Esta pequeña fracción de vértices se conoce como centros (hubs).
En estos casos la distribución del grado tiene una cola larga a la derecha. Esto se traduce en un decaimiento aproximadamente lineal en la frecuencia logarítmica en función del grado logarítmico.
La distribución de la ley de potencias (power law distribution) señala que la distribución del grado d es de la forma
f_d = \mathrm{c}\,d^{-\alpha}\,,\qquad \mathrm{c}>0\,,\qquad \alpha>1\,,
lo que en escala log corresponde a
\log f_d = \log \mathrm{c} - \alpha\log d\,.
\mathrm{c} se denomina constante de normalización y \alpha exponente de la ley de potencias (similar a la distribución de Pareto).
Libre de escala
Las redes que satisfacen este tipo de distribución del grado se denominan libres de escala (scale free) dado que
f_{a\,d} = \mathrm{c}\, (a\,d)^{-\alpha} = a^{-\alpha}\,f_d\,.
En una red libre de escala, algunos nodos están altamente conectados, es decir, poseen un gran número de enlaces a otros nodos, aunque el grado de conexión de casi todos los nodos es bastante bajo.
Distribución de Grados y Conectividad Local
Distribución de grado
dd <-degree_distribution(g)
Grado promedio de los vecinos (GPV) más cercados de orden 1
mnd <-knn(graph = g, vids =V(g))$knnmean(d[as.numeric(neighbors(graph = g, v =1))])
[1] 2.2
Visualización
Code
par(mfrow =c(1,2))plot(NA, NA, type ="n", xlim =c(0,110), ylim =c(0,0.1), xlab ="Grado", ylab ="Densidad", main ="Distribución de grado")hist(d, freq = F, col ="lightskyblue", border ="royalblue", add = T)plot((0:max(d))[dd !=0], dd[dd !=0], log ="xy", pch =16, col =adjustcolor("royalblue", 0.5), xlab ="Log-grado", ylab ="Log-densidad", main ="Distribución de grado (log-log)")
Visualización: GPV vs. grado
Code
plot(x = d, y = mnd, log ="xy", pch =16, col =adjustcolor("yellow3", 0.5), xlab ="Log-grado", ylab ="Log-grado promedio de los vecinos")
Centralidad
Las medidas de centralidad están diseñadas para cuantificar la “importancia” de los nodos de una red.
Centralidad de cercanía (closeness centrality).
Centralidad de intermediación (betweenness centrality).
Centralidad propia (eigenvector centrality).
Existen versiones normalizadas de todas las medidas para facilitar la comparación entre grafos y otras medidas. La normalización se logra multiplicando por una constante apropiada.
Existen versiones para redes dirigidas y ponderadas.
Centralidad de cercanía
Un vértice se considera “importante” si está “cerca” de muchos otros vértices:
c_{\textsf{C}}(v) = \frac{1}{\sum_{u\in V} \textsf{d}(v,u)}
donde \textsf{d}(v,u) es la distancia geodésica entre los vértices u y v de V.
ejemplo
# distanciasD <-distances(graph = g)# closeness centraliy no normalizadahead(cbind(closeness(graph = g, normalized = F), 1/apply(X = D, MARGIN =1, FUN = sum), 1/apply(X = D, MARGIN =2, FUN = sum)), n =5)
Un vértice se considera “importante” si se encuentra “entre” otros pares de vértices.
Los vértices que se encuentran en muchos caminos son más críticos para el proceso de comunicación:
c_{\textsf{B}}(v) = \sum_{s,t\in V:s\neq t\neq v} \frac{\sigma(s,t\mid v)}{\sigma(s,t)}
donde \sigma(s,t\mid v) es el número total de caminos más cortos entre s y t que pasan por v, y \sigma(s,t) es el número total de caminos más cortos entre s y t (independientemente de si pasan por v o no).
# betweenness centraliy no normalizadahead(x =betweenness(graph = g, normalized = F), n =5)
Un vértice se considera “importante” si sus vecinos son a su vez “centrales”:
c_{\textsf{E}}(v) = \alpha\sum_{\{u,v\}\in E} c(u)
donde \mathbf{c}=(c(1),\ldots,c(n)) es una solución al problema de vectores propios dado por \mathbf{Y}\mathbf{c}=\alpha^{-1}\mathbf{c}, con \mathbf{Y} la matriz de adyacencia, \alpha^{-1} es el valor propio más grande de \mathbf{Y}, y \mathbf{c} es el vector propio correspondiente.
La convención es reportar los valores absolutos de las entradas de \mathbf{c}.
Ejemplo
# matriz de adyacenciaY <-as_adjacency_matrix(g, sparse = F)g <-graph_from_adjacency_matrix(Y)evd <-eigen(Y)# eigen centraliy no normalizadahead(cbind(eigen_centrality(graph = g, scale = F)$vector,eigen_centrality(graph = g, scale = F)$vector, Y%*%c(1/evd$values[1]*(-1)*evd$vectors[,1])), n =5) # vector propio x (-1)
[,1] [,2] [,3]
DavidRacero 0.0189891682 0.0189891682 NaN
laurisarabia 0.0135271692 0.0135271692 NaN
MiguelPoloP 0.0000000031 0.0000000031 NaN
ELTIEMPO 0.0064981914 0.0064981914 NaN
petrogustavo 0.6718769980 0.6718769980 NaN
# eigen centraliy normalizadahead(cbind(eigen_centrality(graph = g, scale = T)$vector,eigen_centrality(graph = g, scale = T)$vector, Y%*%c(1/evd$values[1]*(-1)*evd$vectors[,1])/max(Y%*%c(1/evd$values[1]*(-1)*evd$vectors[,1]))), n =5)
[,1] [,2] [,3]
DavidRacero 0.0282628640 0.0282628640 NaN
laurisarabia 0.0201334013 0.0201334013 NaN
MiguelPoloP 0.0000000046 0.0000000046 NaN
ELTIEMPO 0.0096716979 0.0096716979 NaN
petrogustavo 1.0000000000 1.0000000000 NaN
# top 5ec <-eigen_centrality(graph = g, scale = T)$vectorhead(sort(ec, decreasing = T), n =5)
